#include <math.h>
#include <iostream>
using namespace std;

#include "ProgCommon.h"


#define N 7

struct Point {
    Point( int tx = 0, int ty = 0 )
    {
        x = tx;
        y = ty;
    }

    Point( const Point &that )
    {
        x = that.x;
        y = that.y;
    }

    Point& operator=( const Point &that )
    {
        if ( this != &that ) {
            x = that.x;
            y = that.y;
        }

        return *this;
    }

    int x, y;
};

int n;
Point S[N+1];
Point Y[N+1];
Point T[N+1];

/*
Point S[N+1] = {
        Point( 0, 0 ),
        Point( 1, 2 ),
        Point( 1, 4 ),
        Point( 2, 3 ),
        Point( 3, 2 ),
        Point( 4, 4 )
    };

Point Y[N+1] = {
        Point( 0, 0 ),
        Point( 1, 2 ),
        Point( 3, 2 ),
        Point( 2, 3 ),
        Point( 1, 4 ),
        Point( 4, 4 )
    };
*/

void SortX( Point a[], Point b[], int n )
{
    int i, j, k;
    for ( i = 1; i <= n; i++ ) {
        b[i] = a[i];
    }
    for ( i = 1; i < n; i++ ) {
        k = i;
        for ( j = i + 1; j <= n; j++ ) {
            if ( b[j].x < b[k].x )
                k = j;
        }
        if ( k != i ) {
            Swap( b[i], b[k] );
        }
    }
}

void SortY( Point a[], Point b[], int n )
{
    int i, j, k;
    for ( i = 1; i <= n; i++ ) {
        b[i] = a[i];
    }
    for ( i = 1; i < n; i++ ) {
        k = i;
        for ( j = i + 1; j <= n; j++ ) {
            if ( b[j].y < b[k].y )
                k = j;
        }
        if ( k != i ) {
            Swap( b[i], b[k] );
        }
    }
}

void Show( Point a[],  int n )
{
    printf( "\n" );
    for ( int i = 1; i <= n; i++ ) {
        printf( "(%d, %d)\n", a[i].x, a[i].y );
    }
}

double dist( Point &a, Point &b )
{
    int m = (a.x - b.x) * (a.x - b.x);
    int n = (a.y - b.y) * (a.y - b.y);

    return sqrt( m + n );
}

double cp( int low, int high )
{
    int i, j, k, mid;
    int det = high - low;
    if ( 1 == det ) {
        return dist( S[low], S[high] );
    }
    else if ( 2 == det ) {
        mid = low + 1;
        double ma = dist( S[low], S[mid] );
        double mb = dist( S[low], S[high] );
        double mc = dist( S[mid], S[high] );
        ma = MINER( ma, mb );
        ma = MINER( ma, mc );
        return ma;
    }
    else {
        mid = (low+high)/2;
        int x0 = S[mid].x;
        double det_left = cp( low, mid );
        double det_right = cp( mid+1, high );
        double det_tmp = MINER( det_left, det_right );

        k = 0;
        for ( i = 1; i <= n; i++ ) {
            if ( abs(Y[i].x-x0) <= det_tmp ) {
                k += 1;
                T[k] = Y[i];
            }
        }
        double det_tmp_ex = 2 * det_tmp;
        for ( i = 1; i < k; i++ ) {
            int upit = MINER( i+7, k );
            for ( j = i+1; j <= upit; j++ ) {
                if ( dist( T[i], T[j] ) < det_tmp_ex )
                    det_tmp_ex = dist( T[i], T[j] );
            }
        }

        return MINER( det_tmp, det_tmp_ex );
    }
}


double cp2( Point S[], int &ti, int &tj )
{
    int i, j;
    double det = 100.0f, det_ij;
    int n = tj;

    for ( i = 1; i <= n; i++ ) {
        for ( j = 1; j <= n; j++ ) {
            if ( i != j ) {
                det_ij = dist( S[i], S[j] );
                if ( det_ij < det ) {
                    det = det_ij;
                    ti = i;
                    tj = j;
                }
            }
        }
    }

    return det;
}

bool hasPoint( Point S[], int n, int x, int y )
{
    int i;
    for ( i = 1; i <= n; i++ ) {
        if ( S[i].x == x && S[i].y == y )
            return true;
    }

    return  false;
}

int main()
{
    PROG_BANNER;
    RAND_SEED;

    ConSetColor( FG_CYAN );
    printf( "Prog 3 : ClosePair\n" );
    ConSetColor( COLOR_DEFAULT );

    n = N;
    Point rs[N+1];
    /*
    = {
        Point( 0, 0 ),
        Point( 1, 2 ),
        Point( 3, 2 ),
        Point( 2, 3 ),
        Point( 1, 4 ),
        Point( 4, 4 )
    };
    */
    int i = 1, j, k;
    while ( i <= n ) {
        int tx = RandomInt( 1, 10 );
        int ty = RandomInt( 1, 10 );
        if ( i == 1 || !hasPoint( rs, i-1, tx, ty ) )
            rs[i++] = Point( tx, ty );
    }

    printf( "\nFig show >>\n\n" );

    int curX, curY;
    int baseX, baseY;
    ConGetCurPos( baseX, baseY );
    Point base( baseX, baseY );

    for ( i = 0; i <= 9; i++ ) {
        for ( j = 0; j <= 9; j++ ) {
            ConGotoXY( baseX+i, baseY+j );
            if ( 0 == i ) {
                ConSetColor( FG_GREEN );
                printf( "%d", j );
                ConSetColor( COLOR_DEFAULT );
            }
            else if ( 0 == j ) {
                ConSetColor( FG_GREEN );
                printf( "%d", i );
                ConSetColor( COLOR_DEFAULT );
            }
            else if ( hasPoint( rs, n, i, j ) ) {
                ConSetColor( FG_RED );
                printf( "X" );
                ConSetColor( COLOR_DEFAULT );
            }
            else {
                ConSetColor( FG_GRAY );
                printf( "@" );
                ConSetColor( COLOR_DEFAULT );
            }
        }
    }

    SortX( rs, S, n );
    SortY( rs, Y, n );
    // Show( rs, n );
    printf( "\n\n Result >>" );
    printf( "\n cp1: %f", cp( 1, n ) );
    int ti, tj = n;
    printf( "  cp2: %f", cp2( rs, ti, tj ) );

    printf( "\n" );
    PROG_BANNER;

    ConGetCurPos( curX, curY );
    ConGotoXY( baseX+rs[ti].x, baseY+rs[ti].y );
    ConSetColor( FG_YELLOW );
    printf( "X" );
    ConSetColor( COLOR_DEFAULT );
    ConGotoXY( baseX+rs[tj].x, baseY+rs[tj].y );
    ConSetColor( FG_YELLOW );
    printf( "X" );
    ConSetColor( COLOR_DEFAULT );
    ConGotoXY( curX, curY );
    PROG_PAUSE;
    return 0;
}

